15 Backtracking

Backtracking

• DFS = explore everything down to the leaves.
• Backtracking = DFS + pruning (stop early when partial state can’t lead to a solution).

Examples:

• Sudoku: stop when a number violates a row/column/block.
• Word search: stop when partial path doesn’t match the target prefix.

5. Backtracking (Systematic Search with Undo)

function Backtrack(state):
    if IS_SOLUTION(state):             # Modification Point 1
        PROCESS(state)
        return
    for choice in OPTIONS(state):
        if IS_VALID(choice, state):    # Modification Point 2
            MAKE(choice, state)        # apply choice
            Backtrack(state)           # recurse
            UNMAKE(choice, state)      # undo choice (backtrack)

Modification Points

• Is_Solution: Define when a complete/valid solution has been reached.
• Is_Valid: Prune invalid partial solutions early (pruning = efficiency).
• Process: Collect or count solutions, update a best-so-far.
• Make/Unmake: Modify the state (place/remove queen, assign/unassign value, etc.).

Example: Word search

Look for the word ‘LIFE’ in the graph

graph TD
    L((L))
    O_left((I))
    I((I))
    G((G))
    O_right((O))
    K1((K))
    P((P))
    K2((K))
    F((F))
    E1((E))
    E2((E))
    T((T))

    L --> O_left
    L --> I

    O_left --> G
    O_left --> O_right

    O_right --> K1
    O_right --> P

    I --> K2
    I --> F

    K2 --> E1
    F --> E2
    F --> T

State

These are the data structures:

• G: the graph (fixed input).
• W: the target word ‘LIFE’.
• visited: the set of nodes already used (to avoid reuse).
• path: the sequence of nodes chosen so far (the partial solution).
• u: the current node (graph vertex where we are now).
• i: the index in W being matched next.

Is Solution

We have found a solution if:

• i = length(W) → all letters of the word have been matched,

  or

• path = W → the sequence of nodes forms the target word.

for choice in OPTIONS

• Choices are neighbours of u

• for v in Neighbours(u):

Is Valid

A choice is valid if v

• matches the next character W[i].
• v has not been used before (v ∉ visited).

Make

When we choose a node v:

• Add v to visited.
• Append v to path.
• Advance the index: i ← i + 1.
• Move the current node: u ← v.

Unmake

When we undo the choice (backtrack):

• Remove v from visited.
• Remove v from the end of path.
• Decrement the index: i ← i - 1.
• Restore u to the previous node.

Example: Is G 3‑colourable?

Is a given graph, \(G\), three colourable? Note: In assignment problems you’re exploring choices of values for variables, not neighbours in a graph — so there you can choose vertices/variables in any order

State

Data Structures:

• Graph \(G\) - list of nodes Nodes

• u - current node

• colour - dictionary takes nodes as index and colour value

• colours are integers 0, 1, 2 or 3 (0 means uncoloured)

• visited list - actually just use colour

• c - a current colour

Is Solution

• all nodes visited

• no zeros in colour map

for choice in OPTIONS

• for each colour

Is Valid

• u is not already coloured (colour[u] ≠ 0)

• if neigbors of u are not the same colour

Make / Unmake

update colour[u]

Algorithm

## Algorithm 
G         # graph
Nodes     # array/list of vertices in G, e.g. [v1, v2, ..., vn]
color     # dictionary: vertex -> {0,1,2,3} (0 means uncoloured)
COLORS = [1, 2, 3]

function ColorDFS(pos):
    # Base case: all vertices assigned a color
    if pos = length(Nodes):
        return True

    v ← Nodes[pos]

    # Try each color for v
    for c in COLORS:
        if IsValidColor(v, c):
            color[v] ← c                 # MAKE
            if ColorDFS(pos + 1):        # Recurse to next vertex
                return True
            color[v] ← 0                 # UNMAKE (backtrack)

    return False                         # No color worked for v

function IsValidColor(v, c):
    for w in Neighbours(v):
        if color[w] = c:                 # Adjacent same color? invalid
            return False
    return True